#ifndef JAM_LISTS_HPP
#define JAM_LISTS_HPP

#ifdef _MSC_VER
#pragma once
#endif

#include "jam.hpp"
#include "detail/stack_array.hpp"
#include <boost/shared_ptr.hpp>
#include <boost/intrusive_ptr.hpp>
#include <boost/iterator/iterator_facade.hpp>

#include <boost/utility/value_init.hpp>

///////////////////////////////////////////////////////////////////////////////////////
////// List node (internal implementation-specific class)
///////////////////////////////////////////////////////////////////////////////////////
struct JAMLIB_EXPORT jam_list_node
{
	jam_string value_;
	jam_list_node *next_;
	int refcount_;
private: //This class should not be used directly by clients
	friend class jam_list;
	friend class cache_cleanup;
	friend jam_list_node* make_new_node();

	jam_list_node() : next_(), refcount_(1){};
	~jam_list_node(){};
};

///////////////////////////////////////////////////////////////////////////////////////
////// JAM list iterators (don't ask how it works)
///////////////////////////////////////////////////////////////////////////////////////
class mutable_node_iter : public boost::iterator_facade<
	mutable_node_iter, jam_string, boost::forward_traversal_tag>
{
public:	
	mutable_node_iter() : m_node(0) {}
	explicit mutable_node_iter(jam_list_node* p) : m_node(p){}

	mutable_node_iter(mutable_node_iter const& other) : m_node(other.m_node){}

#if !BOOST_WORKAROUND(__GNUC__, == 2)
private: // GCC2 can't grant friendship to template member functions    
	friend class boost::iterator_core_access;
#endif
	bool equal(mutable_node_iter const& other) const
	{
		return this->m_node == other.m_node;
	}
	void increment()
	{
		assert(m_node);
		m_node = m_node->next_;
	}
	jam_string& dereference() const 
	{
		assert(m_node);
		return m_node->value_;
	}
private:
	friend class const_node_iter;
	jam_list_node* m_node;
};

class const_node_iter : public boost::iterator_facade<
	const_node_iter, jam_string const, boost::forward_traversal_tag>
{
public:	
	const_node_iter() : m_node(0) {}
	explicit const_node_iter(jam_list_node const* p) : m_node(p) {}

	const_node_iter(const_node_iter const& other) : m_node(other.m_node) {}
	const_node_iter(mutable_node_iter const& other) : m_node(other.m_node) {}

#if !BOOST_WORKAROUND(__GNUC__, == 2)
private: // GCC2 can't grant friendship to template member functions    
	friend class boost::iterator_core_access;
#endif 
	bool equal(const_node_iter const& other) const
	{
		return this->m_node == other.m_node;
	}
	bool equal(mutable_node_iter const& other) const
	{
		return this->m_node == other.m_node;
	}

	void increment()
	{
		assert(m_node);
		m_node = m_node->next_;
	}
	jam_string const& dereference() const 
	{
		assert(m_node);
		return m_node->value_;
	}
private:
	friend class mutable_node_iter;
	jam_list_node const* m_node;
};

///////////////////////////////////////////////////////////////////////////////////////
////// JAM list
///////////////////////////////////////////////////////////////////////////////////////
//This structure reperesents a list node. It can be efficiently
//passed by value so there's no need to make it refcounted.
class JAMLIB_EXPORT jam_list : protected jam_list_node //Intentionally not public
{
	jam_list_node *tail_;
	size_t size_;
public:
	typedef mutable_node_iter iterator;
	typedef const_node_iter const_iterator;
	
	jam_list() : size_() {};
	jam_list(const jam_list &other);
	explicit jam_list(const jam_string &str) : size_()
	{
		push_back(str);
	}	
	template<class Iter> jam_list(Iter first, Iter last) : size_()
	{
		append(first,last);
	}
	jam_list& operator = (const jam_string &str);
	jam_list& operator = (const jam_list &other);
	~jam_list(){clear();}
	
	bool empty() const {return size_==0;}
	size_t size() const {return size_;}
	bool operator == (const jam_list &other) const;
	bool size_is_one() const {return size_==1;}
	void hint_list_size(const jam_list &oth){} //No-op. TODO: optimize it

	//Iteration
	iterator begin()
	{
		if (empty())
			return iterator();
		else
		{
			make_unique();
			return iterator(this);
		}
	}
	const_iterator begin() const
	{
		if (empty())
			return const_iterator();
		else
			return const_iterator(this);
	}

	iterator end() {return iterator();}
	const_iterator end() const {return const_iterator();}

	//Access
	jam_string& front();
	const jam_string& front() const;
	jam_string& back();
	const jam_string& back() const;

	//Mutators
	void push_back(const jam_string &val);
	void pop_front();
	template<class Iter> void append(Iter first, Iter last)
	{
		for(Iter f=first;f!=last;++f)
			push_back(*f);
	}	
	//Destructively append one list to another
	void move_tail_from(jam_list &other);
	void clear();

	void swap(jam_list &other) //nothrow
	{
		std::swap(value_,other.value_);
		std::swap(next_,other.next_);
		std::swap(tail_,other.tail_);
		std::swap(size_,other.size_);		
		std::swap(refcount_,other.refcount_);
	}

private:
	void copy_from(const jam_list &other);
	void make_unique();
};

extern JAMLIB_EXPORT const jam_list null_list;

JAMLIB_EXPORT std::ostream& operator << (std::ostream &str,const jam_list &lst);

///////////////////////////////////////////////////////////////////////////////////////
////// List-of-lists implemented as a circular buffer on stack with efficient
////// push_back/push_front/pop_back/pop_front.
///////////////////////////////////////////////////////////////////////////////////////
typedef fixed_size_list<jam_list,JAM_MAX_PARAMS> list_of_lists;

JAMLIB_EXPORT std::ostream& operator << (std::ostream &str,const list_of_lists &lst);

inline const jam_list& get_list_element(const list_of_lists &lst, size_t pos)
{
	return lst[pos];
}

#endif //JAM_LISTS_HPP
